/**
 * Created by asd73 on 2017/8/27.
 */
public class cache {
    public static int partition(int []array,int lo,int hi){
        //三数取中
        int mid=lo+(hi-lo)/2;
        if(array[mid]>array[hi]){
            swap(array[mid],array[hi]);
        }
        if(array[lo]>array[hi]){
            swap(array[lo],array[hi]);
        }
        if(array[mid]>array[lo]){
            swap(array[mid],array[lo]);
        }
        int key=array[lo];

        while(lo<hi){
            while(array[hi]>=key&&hi>lo){
                hi--;
            }
            array[lo]=array[hi];
            while(array[lo]<=key&&hi>lo){
                lo++;
            }
            array[hi]=array[lo];
        }
        array[hi]=key;
        return hi;
    }

    static void swap(int a,int b){
        int temp=a;
        a=b;
        b=temp;
    }
    static void sort(int[] array,int lo ,int hi){
        if(lo>=hi){
            return ;
        }
        int index=partition(array,lo,hi);
        sort(array,lo,index-1);
        sort(array,index+1,hi);
    }

    public static void main(String[] args) {
        String[] strVoid=new String[]{"11","66","2","4","55","22","5","32"};
        int[] array1 = new int[strVoid.length];
        for (int i=0;i<strVoid.length;i++){
            array1[i]=Integer.parseInt(strVoid[i]);
        }
        sort(array1,0,array1.length-1);
        for (int i=0;i<array1.length;i++){
            System.out.print(array1[i]+" ");
        }
        System.out.println();
    }

}
